package com.yanyeori.algorithm.redblacktree;

/**
 * @author chenkuan
 * @desc 红黑树
 * @date 2021/3/18 018 16:48
 */
@SuppressWarnings("unchecked")
public class RedBlackTree<T> {

    //红色
    private final int R = 0;
    //黑色
    private final int B = 1;
    //根节点
    private Node<T> root;

    class Node<T> {
        //数据
        T data;
        //颜色
        int color = R;
        //左节点
        Node left;
        //右节点
        Node right;
        //父节点
        Node parent;

        public Node(T data) {
            this.data = data;
        }
    }

    /**
     * 插入
     */
    public void insert(Node<T> root, T data) {
        if (root.data.hashCode() < data.hashCode()) {
            if (root.right == null) {
                root.right = new Node<T>(data);
            } else {
                insert(root.right, data);
            }
        } else {
            if (root.left == null) {
                root.left = new Node<T>(data);
            } else {
                insert(root.left, data);
            }
        }
    }

    /**
     * 左旋
     */
    public void leftRotate(Node<T> node) {
        if (node.parent == null) {
            Node e = root;
            Node s = e.right;

            e.right = s.left;
            s.left.parent = e;

            e.parent = s;
            s.left = e;

            s.parent = null;

            root = s;
        }
    }

    /**
     * 右旋
     */
    public void rightRotate(Node<T> node) {
        if (node.parent == null) {
            Node s = root;
            Node e = s.left;

            s.left = e.right;
            e.right.parent = s;

            s.parent = e;
            e.right = s;

            e.parent = null;

            root = e;
        }
    }
}
